"""
题目：判断一个有向图中是否存在环。
"""

class Graph:
    def __init__(self, is_directed=True):
        self.vertices = {}
        self.is_directed = is_directed  # 默认为有向图

    def add_vertex(self, vertex):
        if vertex not in self.vertices:
            self.vertices[vertex] = []

    def add_edge(self, v1, v2):
        self.add_vertex(v1)
        self.add_vertex(v2)
        self.vertices[v1].append(v2)

    """
    代码逻辑核心
    该算法通过深度优先搜索（DFS）结合两个集合（visited和rec_stack）来检测有向图中的环：
    visited记录所有已遍历的顶点，避免重复遍历。
    rec_stack记录当前递归路径上的顶点，若在递归过程中再次遇到rec_stack中的顶点，说明存在环（当前路径形成了回路）。
    当一个顶点的所有邻接顶点处理完毕后，会将其从rec_stack中移除（回溯过程），保证rec_stack始终只记录当前路径的顶点。
    """
    """检测有向图中是否存在环（DFS实现）"""
    def has_cycle(self):
        visited = set() # 所有已访问的顶点
        """
        比如：
        A → B → C
            ↓
            D
        在整个过程中，rec_stack始终只包含 “当前正在遍历的路径” 上的顶点：
        比如访问到 C 时，当前路径是A→B→C，rec_stack就精确记录这三个顶点。
        当 C 处理完回溯到 B 时，路径缩短为A→B，rec_stack也同步移除 C。
        这种机制能准确判断环：如果在遍历中遇到一个“已经在rec_stack中的顶点”，说明当前路径出现了回路（例如A→B→C→A，访问 A 时发现 A 已在rec_stack中，即判定有环）。
        """
        rec_stack = set()       # 当前递归路径中的顶点 始终只保留 “当前正在遍历的路径” 上的顶点
        def dfs(vertex):
            # 如果顶点在当前递归路径中，说明存在环
            if vertex in rec_stack:
                return True
            # 如果顶点已访问(in visited体现)且不在当前路径中(in rec_stack分支没进去的体现)，无需再处理 避免对已经确定无环的路径进行重复遍历，提高算法效率 这步要好好体会!!!
            if vertex in visited:
                return False
            # 将顶点加入已访问和当前递归路径
            visited.add(vertex)
            rec_stack.add(vertex)
            # 检查所有邻接顶点
            for neighbor in self.vertices[vertex]:
                if dfs(neighbor):
                    return True
            # 回溯, 从当前递归路径中移除顶点！！！ 这步也很重要 要理解递归回溯过程中rec_stack的动态变化
            rec_stack.remove(vertex)
            return False
        # 检查所有未访问的顶点
        for vertex in self.vertices:
            if vertex not in visited:
                if dfs(vertex):
                    return True
        return False  # 未发现环

# 测试
# 有环图 (A->B->C->A)
graph1 = Graph()
graph1.add_edge('A', 'B')
graph1.add_edge('B', 'C')
graph1.add_edge('C', 'A')
print(graph1.has_cycle())  # 输出: True

# 无环图 (A->B->C)
graph2 = Graph()
graph2.add_edge('A', 'B')
graph2.add_edge('B', 'C')
print(graph2.has_cycle())  # 输出: False
